package com.atwulidun.greedyalgorithm05;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class BroadcastsCoverage {
    public static void main(String[] args) {
        // 创建一个hashMap来保存每个电台以及其可以覆盖的城市
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();

        // 用hashSet来保存每个电台可以覆盖的城市
        // 电台1
        HashSet<String> hashSet1 = new HashSet<String>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        // 电台2
        HashSet<String> hashSet2 = new HashSet<String>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        // 电台3
        HashSet<String> hashSet3 = new HashSet<String>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        // 电台4
        HashSet<String> hashSet4 = new HashSet<String>();
        hashSet4.add("上海");
        hashSet4.add("天津");
        // 电台5
        HashSet<String> hashSet5 = new HashSet<String>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        // 加入到 map
        broadcasts.put("K1", hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);

        // allAreas 存放所有的地区
        HashSet<String> allAreas = new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");


        // 定义一个临时的hashSet来存放遍历每个电台时其覆盖地区与当前allAreas存放地区的交集
        HashSet<String> tempSet = new HashSet<>();

        // 定义一个ArrayList来存放被选出来的电台
        List<String> selects = new ArrayList<>();

        // 只要allAreas不为空，那么就要对电台进行遍历，直到所有地区都被覆盖，allAreas中的地区被删除光为止
        while (allAreas.size() != 0) {
            // 定义一个变量来存储每次遍历完所有电台后与allAreas有最大交集的那个电台
            String maxKey = null;
            // 定义一个变量来存储每次遍历完所有电台后与allAreas的最大交集的size
            int maxSize = -1;
            // 接下来对所有电台进行遍历
            for (String s : broadcasts.keySet()) {
                // 特别注意：因为tempSet是循环利用的，因此在遍历到每一个电台之前都要对其清空！！！！！！！！！！！！！！！！！！！！！！！！！！！
                tempSet.clear();
                // 获取当前电台所覆盖的区域
                HashSet<String> areas = broadcasts.get(s);
                // 将当前电台所覆盖的区域加入到tempSet中
                tempSet.addAll(areas);
                // 求当前电台所覆盖区域与allAreas的交集
                tempSet.retainAll(allAreas);
                // 如果是刚进for循环的第一个电台，那么把第一个电台的key赋给maxKey，把第一个电台的tempSet.size()赋给maxSize
                // 等第二个电台就会进行tempSet.size() > maxSize的判断了
                if (maxSize == -1 || tempSet.size() > maxSize) {
                    maxSize = tempSet.size();
                    maxKey = s;
                }
            }
            // for循环完成后，maxKey不可能为null，maxSize也不可能为-1
            // 将maxKey对应的电台加入到selects中
            selects.add(maxKey);
            // 删除maxKey对应的电台所能覆盖到的allAreas中的区域
            allAreas.removeAll(broadcasts.get(maxKey));
        }

        // 打印输出最后的结果
        System.out.println(selects);
    }
}
